package Sort;

/**
 * @author zhangmin
 * @create 2022-04-18 13:34
 */
public class Heap<T extends Comparable<T>> {
    private T[] heap;
    private int n=0;
    public Heap(int size){
        this.heap= (T[]) new Comparable[size+1];
    }

    public boolean isEmpty(){
        return n==0;
    }
    public int size(){
        return n;
    }
    private boolean less(int i,int j){
        return heap[i].compareTo(heap[j])<0;
    }
    private void sweep(int i,int j){
        T t=heap[i];
        heap[i]=heap[j];
        heap[j]=t;
    }
    //上浮：当一个节点比父节点大，那么需要交换，直到满足要求
    private void swim(int k){
        while (k>1&&less(k/2,k)){
            sweep(k/2,k);
            k=k/2;
        }
    }
    //下沉：当一个节点比子节点来的小，那也需要向下不断交换
    private void sink(int k){
        while (2*k<=n){
            int j=2*k;
            if (j<n&&less(j,j+1)){
                j++;
            }
            if (!less(k,j)){
                break;
            }
            sweep(k,j);
            k=j;
        }
    }
    //插入元素
    public void insert(Comparable v){
        heap[++n]= (T) v;
        swim(n);
    }
    //删除最大元素
    public T deleteMax(){
        T max=heap[1];
        sweep(1,n--);
        heap[n+1]=null;
        sink(1);
        return max;
    }

}
